package leetcode.editor.cn.twoPointer;

//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 
// 👍 3554 👎 0

class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
        solution.longestPalindrome("babad");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * @Time:
         * @Space:
         * @Author: 赖锦帆
         * @Date: 2021-04-22 11:03
         * 双指针：从中间向两侧
         */
        public String longestPalindrome(String s) {
            String maxS = "";
            for (int i = 0; i < s.length(); i++) {
                String s1 = palindrome(s,i,i);
                String s2 = palindrome(s,i,i+1);
                String max = s1.length()>s2.length()?s1:s2;
                if (max.length()>maxS.length())
                    maxS = max;
            }
            return maxS;
        }
        //寻找以l，r为中心的回文子串
        private String palindrome(String s, int l, int r){
            while (l>=0&&r<=s.length()-1&&s.charAt(l)==s.charAt(r)){
                l--;
                r++;
            }
            return s.substring(l+1,r);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
